#include<iostream>
#include<vector>
#include<iomanip>
#include<string>
#include<queue>
#include<functional>
using namespace std;

typedef struct HuffmanNode
{
	int weight;
	int parent;
	int left;
	int right;
	operator int() const { return weight; }
};

class HuffmanTree
{
public:
	HuffmanTree(int _n, vector<int>& _weight)
		:n(_n), weight(_weight)
	{
		huffTree.resize(2 * n);
		for (int i = 1; i <= n; i++)
		{
			huffTree[i].weight = weight[i - 1];
		}
		CreateHuffmanTree();
		CreatHuffmanCode();
	}
	~HuffmanTree() {}
	void Print_HuffmanTreeAndCode()
	{
		int len = huffTree.size();
		cout << setw(8) << "index" << setw(8) << "weight" << setw(8) << "parent" << setw(8) << "left" << setw(8) << "right" << setw(8) << "code" << endl;
		for (int i = 1; i < len; i++)
		{
			cout << setw(8) << i;
			cout << setw(8) << huffTree[i].weight;
			cout << setw(8) << huffTree[i].parent;
			cout << setw(8) << huffTree[i].left;
			cout << setw(8) << huffTree[i].right;
			if(i <= n) cout << setw(8) << huffmanCode[i-1] << endl;
			else cout << endl;
		}
	}
	vector<string> GetHuffmanCode() { return huffmanCode; }
private:
	void CreateHuffmanTree()
	{
		typedef struct StkNode
		{
			int index;
			int weight;
			operator int() const { return weight; }
		};
		priority_queue<StkNode, vector<StkNode>, greater<StkNode>> pque;
		for (int i = 0; i < n; i++)
		{
			StkNode tmp = { i+1, weight[i] };
			pque.push(tmp);
		}
		int k = n + 1;
		while (!pque.empty())
		{
			if (pque.empty()) break;
			StkNode left = pque.top(); pque.pop();
			if (pque.empty()) break;
			StkNode right = pque.top(); pque.pop();
			huffTree[k].weight = left.weight + right.weight;
			StkNode tmp = { k, huffTree[k].weight };
			pque.push(tmp);
			huffTree[k].parent = 0;
			huffTree[k].left = left.index;
			huffTree[k].right = right.index;
			huffTree[left.index].parent = k;
			huffTree[right.index].parent = k;
			k++;
		}
	}
	void CreatHuffmanCode()
	{
		for (int i = 1; i < n + 1; i++)
		{
			int pa = huffTree[i].parent;
			int index = i;
			string str;
			while (pa != 0)
			{
				char c = huffTree[pa].left == index ? '0' : '1';
				str.insert(str.begin(), c);
				index = pa;
				pa = huffTree[pa].parent;
			}
			huffmanCode.push_back(str);
		}
	}
private:
	int n;
	vector<int> weight;
	vector<HuffmanNode> huffTree;
	vector<string> huffmanCode;
};

int main()
{
    int n = 8;
	vector<int> vec = { 5, 29, 7, 8, 14, 23, 3, 11 }; 
	HuffmanTree huff(vec.size(), vec);
	huff.Print_HuffmanTreeAndCode();
	vector<string> huffmanCode = huff.GetHuffmanCode();
	cout << endl;
	cout << setw(8) << "weight" << setw(8) << "Code" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << setw(8) << vec[i] << setw(8) << huffmanCode[i] << endl;
	}

	return 0;
}
/*
index  weight  parent    left   right
1       5       9       0       0
2      29      14       0       0
3       7      10       0       0
4       8      11       0       0
5      14      12       0       0
6      23      13       0       0
7       3       9       0       0
8      11      11       0       0
9       8      10       7       1
10      15      12       3       9
11      19      13       4       8
12      29      14       5      10
13      42      15      11       6
14      58      15       2      12
15     100       0      13      14
*/